//优先队列是一种特殊的队列，其中的元素按照一定的优先级进行排序，每次取出的元素都是优先级最高的。它的底层实现通常使用堆（heap）数据结构。
//需要包含头文件#include<queue>



#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int main()
{
	//创建对象
	priority_queue<int, vector<int>, less<int>>	pq;
	//定义了一个存储int整数的优先队列，使用less作为比较函数（默认）,元素从大到小排列
	//比较函数也可以是greater，则从小到大，还可以是自定义仿函数


	//插入元素	
	pq.push(3);
	pq.push(5);	
	pq.push(8);		//会自动排序


	//访问(top)和移除(pop)元素
	cout << pq.top() << endl;	//访问优先级最高的元素
	pq.pop();				//移除优先级最高的元素
	cout << pq.top() << endl;


	//pq.empty();		//检查队列是否为空，返回bool值

	return 0;
}






//自定义仿函数

class Person
{
public:
	int m_age;
	string m_name;

	Person(string name, int age) :m_name(name), m_age(age) {};
};

class MyCompare
{
public:
	bool operator()(Person p1, Person p2)	//重载() 仿函数
	{
		return p1.m_age > p2.m_age;		//按年龄从小到大
	}
		
};

int main()
{
	Person p1("张三", 20);
	Person p2("李四", 19);
	Person p3("王五", 42);
	Person p4("赵六", 28);
	Person p5("孙七", 32);
	Person p6("周八", 17);
	Person p7("吴九", 23);


	priority_queue<Person, vector<Person>, MyCompare> pq;
	pq.push(p1);
	pq.push(p2);
	pq.push(p3);
	pq.push(p4);
	pq.push(p5);
	pq.push(p6);
	pq.push(p7);
	pq.push(Person("郑十", 39));

	while (!pq.empty())
	{
		Person p = pq.top();
		cout << "姓名: " << p.m_name << "\t年龄:" << p.m_age << endl;
		pq.pop();
	}

	return 0;
}

/*
姓名: 周八      年龄:17
姓名: 李四      年龄:19
姓名: 张三      年龄:20
姓名: 吴九      年龄:23
姓名: 赵六      年龄:28
姓名: 孙七      年龄:32
姓名: 郑十      年龄:39
姓名: 王五      年龄:42

*/





////优先级队列(#include<queue>)总结
/*
priority_queue<int, vector<int>, greater<int> > 容器名;
priority_queue是不允许随机访问，只能访问队列首部的元素，也只能对首部元素进行出队.
int类型可以更改为其他类型包括自定义类型(自定义类型时需要在最后加入仿函数mycmp)
greater是大顶堆，即队首为最大值, less为小顶堆
默认定义为大顶堆 : priority_queue<储存的类型> 容器名;
成员函数:
empty() 如果优先队列为空，则返回真
pop() 删除第一个元素
push() 加入一个元素
size() 返回优先队列中拥有的元素的个数
top() 返回优先队列中有最高优先级的元素
*/



